package leetcode.editor.cn.q1_300.q200;
//给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 
//
// 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 
//
// 请不要使用除法，且在 O(n) 时间复杂度内完成此题。 
//
// 
//
// 示例 1: 
//
// 
//输入: nums = [1,2,3,4]
//输出: [24,12,8,6]
// 
//
// 示例 2: 
//
// 
//输入: nums = [-1,1,0,-3,3]
//输出: [0,0,9,0,0]
// 
//
// 
//
// 提示： 
//
// 
// 2 <= nums.length <= 10⁵ 
// -30 <= nums[i] <= 30 
// 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内 
// 
//
// 
//
// 进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。） 
//
// 👍 1470 👎 0

import java.util.Arrays;

/**
 * 将所有除了 0 以外的数相乘，然后遍历数组，用乘积除以 nums[i] 得到结果
 * <p>
 * 注意全是 0 的情况
 */
public class Q238_ProductOfArrayExceptSelf {
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] productExceptSelf(int[] nums) {
            // 乘积
            int ji = 1;
            // 0 的数量
            int zeroNum = 0;
            for (int num : nums) {
                if (num == 0) {
                    zeroNum++;
                    continue;
                }
                ji *= num;
            }

            int[] arr = new int[nums.length];
            if (zeroNum > 0) {
                if (zeroNum > 1) {
                    for (int i = 0; i < nums.length; i++) {
                        arr[i] = 0;
                    }
                } else {
                    for (int i = 0; i < nums.length; i++) {
                        arr[i] = nums[i] == 0 ? ji : 0;
                    }
                }
            } else {
                for (int i = 0; i < nums.length; i++) {
                    arr[i] = ji / nums[i];
                }
            }

            return arr;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q238_ProductOfArrayExceptSelf().new Solution();
        // TO TEST
        System.out.println(Arrays.toString(solution.productExceptSelf(new int[]{0, 4, 0})));
        System.out.println(Arrays.toString(solution.productExceptSelf(new int[]{0, 0})));
        System.out.println(Arrays.toString(solution.productExceptSelf(new int[]{1, 2, 3, 4})));
        System.out.println(Arrays.toString(solution.productExceptSelf(new int[]{-1, 1, 0, -3, 3})));
    }
}